Will, et al. Supplemental Material – “Structure-based Whole Genome Realignment Reveals Many Novel Non-coding RNAs”

A novel reference-based banding technique for multiple alignment We introduce a banding technique for multiple sequence alignment. The general idea is to constrain the space of alignments considered to those that deviate by a small amount from a given reference alignment. The parameter ∆ specifies the maximum amount of deviation. Informally, a residue or nucleotide in the reference alignment can be repositioned up to ∆ positions up or downstream. In this way, banding enables a systematic “realignment ” of a reference. Our banding technique can be applied to any dynamic programming (DP) alignment algorithm that recursively computes optimal subalignments. Computation can be visualized over a DP matrix where each entry corresponds to a “cut”, i.e. a split into a set of prefix subalignments and a set of suffix subalignments. A “trace ” is a continuous path of matrix entries that correspond to a complete alignment. Supplementary Figure 1 illustrates the trace of a reference alignment AR and the set of all cuts within a deviation of 1 from AR. Traces through these cuts correspond to complete alignments within a deviation of 1 from AR. These alignments are exactly those considered under banding with ∆ = 1. In the following sections we will formalize our banding technique under the notions of cuts and ∆-deviation. We will describe banding for pairwise alignment and extend to progressive multiple alignment. Finally, we will describe the implementation of banding for the structure-based multiple RNA alignment tool LocARNA (Will et al. 2007).